package LeetCode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LC_651_4KeysKeyboard {

    public static void main(String[] args) {

    }

    public class Solution {
        Set<String> s = new HashSet<>();
        Set<String> ss = new HashSet<>();
        List<TreeNode> ret = new ArrayList<>();

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            t(root, new StringBuilder());
            return ret;
        }

        private String t(TreeNode root, StringBuilder sb) {
            if (root == null) return "null&";
            sb.append(root.val).append("&");
            sb.append(t(root.left, new StringBuilder()));
            sb.append(t(root.right, new StringBuilder()));
            String fi = sb.toString();
            if (s.contains(fi)) {
                if (!ss.contains(fi)) {
                    ret.add(root);
                    ss.add(fi);
                }
            } else {
                s.add(fi);
            }
            return fi;
        }
    }

}